package top100.binarysearch;

import top100.array.Solution189;
import utils.Utils;

import static utils.Utils.lowerBound;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/21 9:40
 * @description:
 */
public class Solution240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int x = 0, y = matrix[0].length-1;
        while (x < matrix.length && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }
        return false;
    }
    public boolean searchMatrix2(int[][] matrix, int target) {
        // 遍历矩阵的每一行
        for (int[] row : matrix) {
            // 使用lowerBound查找当前行中第一个大于等于target的元素位置
            int index = lowerBound(row, 0, row.length, target);

            // 检查找到的位置是否有效且元素等于目标值
            if (index < row.length && row[index] == target) {
                return true;
            }
        }
        // 所有行都搜索完毕仍未找到
        return false;
    }

    public static void main(String[] args) {
        Solution240 solution = new Solution240();
        int [][] matrix = {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(solution.searchMatrix(matrix,5));

    }
}
